//
// Created by 86188 on 2022/9/15.
//

#ifndef TREEPROJECT_HEAP_H
#define TREEPROJECT_HEAP_H
void HeadAdjust(int *pInt, int i, int len);

/**
 * 建立大根堆算法
 * @param A
 * @param len
 */
void BuildMaxHeap(int A[],int len){
    int i;
    for (i = len/2; i>0; i--)
        HeadAdjust(A,i,len);
}

/**
 * HeadAdjust将元素k为根的子树进行调整
 * @param A
 * @param k
 * @param len
 */
void HeadAdjust(int A[], int k, int len) {
    A[0] = A[k];    // A[0]暂存子树的根结点
    int i;
    for (i = 2*k; i <=len ; i=i*2) {    // 沿key较大的子结点向下筛选
        if(i<len&&A[i]<A[i+1])
            i++;    // 取key较大的子结点的下标
        if(A[0]>=A[i]) break;   // 筛选结束
        else{
            A[k] = A[i];    // 将A[i]调整到双亲结点上
            k = i;          // 修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0];            // 被筛选结点的值放入最终量位置
}

/**
 * 交换堆顶和堆底元素的函数
 * @param A
 * @param i
 */
void Swap(int A[],int i){
    int p = A[i];
    A[i] = A[1];
    A[1] = p;
}

/**
 * 堆排序算法: 王道视频课”堆排序“，第十分钟
 * @param A
 * @param len
 */
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);              // 初始建堆
    int i;
    for (i = len; i>1 ; i--) {   // n-1趟交换和建堆过程
        Swap(A,i);                   // 输出堆顶元素(和堆底元素交换)
        HeadAdjust(A,1,i-1); // 调整，把剩余的i-1个元素整理成堆
    }
}
#endif //TREEPROJECT_HEAP_H
